#include <algorithm>
#include <cstdlib>  // Header file needed to use srand and rand
#include <iostream>
#include <unordered_set>

#include "pulse_optical.h"

Pulse_optical::~Pulse_optical(){
    
    if (cost_map_) {
        delete[] cost_map_;
        cost_map_ = nullptr;
    }
    if (delay_map_) {
        delete[] delay_map_;
        delay_map_ = nullptr;
    }
    if (visited_) {
        delete[] visited_;
        visited_ = nullptr;
    }
    if (info_) {
        delete[] info_;
        info_ = nullptr;
    }
    
}

void Pulse_optical::SetupTopology(Graph* graph) {
    graph_ = graph;
    num_nodes_ = graph_->NodeSize();
    cost_map_ = new int[num_nodes_];
    delay_map_ = new int[num_nodes_];
    visited_ = new bool[num_nodes_];
    info_ = new PulseInfo[num_nodes_]();
    Q_tent = std::vector<std::priority_queue<Lable, std::vector<Lable>, cmp>>(num_nodes_);
    Q_clear = std::vector<std::priority_queue<Lable, std::vector<Lable>, cmp>>(num_nodes_);
    L_perm = std::vector<std::vector<Lable>>(num_nodes_);
    L_clear = std::vector<std::vector<Lable>>(num_nodes_);
}

void Pulse_optical::Check(){}

std::vector<int> Pulse_optical::Intersection(std::vector<int> v1, std::vector<int> v2){
    std::unordered_set<int> result_set; // 用于存放结果
    std::unordered_set<int> nums_set(v1.begin(), v1.end());
        for (int num : v2) {
            // 发现v2的元素 在nums_set里又出现过
            if (nums_set.find(num) != nums_set.end()) {
                result_set.insert(num);
            }
        }
    return std::vector<int>(result_set.begin(), result_set.end());
}

 bool Pulse_optical::Judge(std::vector<int> v1,std::vector<int> v2){
    std::vector<int> result = Intersection(v1, v2); 
    //v1包含于v2返回true
    if(result.size()==v1.size()){
        return true;
    }else{
        return false;
    }
 }


Path Pulse_optical::FindPath(const Flow& flow) {
    // store the result of dijkstras in cost_map and delay_map
    flow_ = flow;
    Generic_Dijkstra(flow_.to, cost_map_, true);
    Generic_Dijkstra(flow_.to, delay_map_, false);
    // Reset Pulse Algorithm
    for (int i = 0; i < num_nodes_; ++i) {
        visited_[i] = false;
        info_[i].Clear();
    }
    NodeId start = flow_.from;
    visited_[start-1] = true;
    tmp_min_delay = kMaxValue; // 记录最低延迟
    results_.clear();
    
    // Start pulse algorithm
    Path path;
    path.path_info.push_back(start);
    path.cost = 0;
    path.delay = 0;
    num_iterations_ = 0;
    Dfs(start, path);
   
    return results_.back();
}

//Dijkstra算法 flag为真时对cost，为假时对delay
void Pulse_optical::Generic_Dijkstra(NodeId dst,  int* node_to_dst_dis, bool flag){
    node_to_dst_dis[dst-1] = 0; //终点到终点距离为零 
    NodeId begin = 1; //标记开始的节点
    for(int i = 1; i<num_nodes_;i++){
        for (int i = 0; i < num_nodes_; ++i) {
            visited_[i] = false;
        }
       if(i<dst){
           begin = i;
        }else{
            begin = i+1;
        }
        Q_tent[begin-1].push(l_0);
        while(!Q_tent.empty()){ 
            Lable temp_l = {100, 0, 0,Omega};
            int mark = -1;
            for(int i = 0;i<num_nodes_;i++){
                if(!Q_tent[i].empty()){
                    if(temp_l.weight>Q_tent[i].top().weight){
                        temp_l = Q_tent[i].top();
                        mark = i; //记录temp_l对应的节点
                    }   
                }
            }
           
            NodeId temp_v =0;
            if(temp_l.Edge_id==0){
                temp_v = begin;
            }else{
                Link* temp_e = graph_->GetIdLinks(temp_l.Edge_id);
                //std::cout<<temp_l.Edge_id;
                temp_v = temp_e->ter_id;
            } 

             Q_tent[mark].pop(); //移出Q_tent
            L_perm[mark].emplace_back(temp_l); //加入L_perm
            visited_[mark] = true;

            //std::cout<<"Node__  "<<temp_v<<"\n";
            if(temp_v == dst){
                break;
            }
            for(Link* edge_next: graph_->GetEgressLinks(temp_v)){
                if(flag){
                    Relax_cost(edge_next,temp_l);
                }else{
                    Relax_delay(edge_next,temp_l);
                }
            }
         
        }     
        node_to_dst_dis[begin-1] = L_perm[dst-1][0].weight;
        //std::cout<<node_to_dst_dis[begin-1]<<"\n";
        L_perm = L_clear;
        Q_tent = Q_clear;
        } 
    }
    


void Pulse_optical::Relax_cost(Link* e, Lable l){
    //std::cout<<"Relax_cost\n";
    int cost_new = 0;
    if(e->cost>=0){
        int cost = e->cost;
        int cost_new = cost + l.weight;
    }   
    std::vector<int> CU_now = l.CU; 
    std::vector<int> AU_now = e->A_units;
    NodeId v_next = e->ter_id;
    //CU_new是AU_now和CU_now的交集
    std::vector<int> CU_new = Intersection(CU_now, AU_now);

    if(CU_new.empty()){
        return;
    }

    if(visited_[v_next-1]){
        return;
    }
    
    //std::cout<<v_next<<"\n";
    Lable l_new = {cost_new, e->link_id, e->link_state,CU_new};
    //在L_perm中删除掉次于l_new的标签
    for(auto iter=L_perm[v_next-1].begin();iter!=L_perm[v_next-1].end(); ){
    Lable temp = *iter;
     if( Lable_Judge(l_new, temp))
          iter = L_perm[v_next-1].erase(iter);
      else
            iter ++ ;    
    }
    //std::cout<<"L OK\n";
    //在Q_tent中删除掉次于l_new的标签
    std::vector<Lable> set_temp = {};
    for(int i=0; i<Q_tent[v_next-1].size();i++){
        if(!Q_tent[v_next-1].empty()){
            Lable temp = Q_tent[v_next-1].top();
            Q_tent[v_next-1].pop();
            if(Lable_Judge(l_new, temp)){
            }else{
                set_temp.emplace_back(temp);
            }
        }
    }
    for(int i = 0;i<set_temp.size();i++){
        Lable temp = set_temp[i];
        Q_tent[v_next-1].push(temp);
    }
    //std::cout<<"Q OK\n";
    Q_tent[v_next-1].push(l_new);
}

void Pulse_optical::Relax_delay(Link* e, Lable l){
    int delay = e->delay;
    int delay_new = delay + l.weight;
    std::vector<int> CU_now = l.CU;
    std::vector<int> AU_now = e->A_units;
    int v_next = e->ter_id;
    //CU_new是AU_now和CU_now的交集
    std::vector<int> CU_new = Intersection(CU_now, AU_now);

    if(CU_new.empty()){
        return;
    }

    if(visited_[v_next-1]){
        return;
    }
    
    //std::cout<<v_next<<"\n";
    Lable l_new = {delay_new, e->link_id, e->link_state,CU_new};
    //在L_perm中删除掉次于l_new的标签
    for(auto iter=L_perm[v_next-1].begin();iter!=L_perm[v_next-1].end(); ){
    Lable temp = *iter;
     if( Lable_Judge(l_new, temp))
          iter = L_perm[v_next-1].erase(iter);
      else
            iter ++ ;    
    }
    //std::cout<<"L OK\n";
    //在Q_tent中删除掉次于l_new的标签
    std::vector<Lable> set_temp = {};
    for(int i=0; i<Q_tent[v_next-1].size();i++){
        if(!Q_tent[v_next-1].empty()){
            Lable temp = Q_tent[v_next-1].top();
            Q_tent[v_next-1].pop();
            if(Lable_Judge(l_new, temp)){
            }else{
                set_temp.emplace_back(temp);
            }
        }
    }
    for(int i = 0;i<set_temp.size();i++){
        Lable temp = set_temp[i];
        Q_tent[v_next-1].push(temp);
    }
    //std::cout<<"Q OK\n";
    Q_tent[v_next-1].push(l_new);
}

bool Pulse_optical::Lable_Judge(Lable& l1, Lable& l2){
    // 若l1优于l2，则返回true
    std::vector<int> CU1 = l1.CU;
    std::vector<int> CU2 = l2.CU;
    std::vector<int> result = Intersection(CU1, CU2); //求CU1和CU2的交集
    if(l1.weight<l2.weight && result.size()<=CU1.size()){
        return true;
    }else if (l1.weight<=l2.weight && result.size()<CU1.size())
    {
        return true;
    }else{
        return false;
    }
}

void Pulse_optical::Dfs(NodeId u, Path& path) {
    ++num_iterations_;
    if (u == flow_.to) {
        if (path.delay >= tmp_min_delay) {
            return;
        }
        if (path.cost > limit_cost) {
            return;
        }
        tmp_min_delay = path.delay;
        results_.push_back(path);
        std::cout<<tmp_min_delay<<"push_back\n";
        return;
    }

    // pruning strategies
    /*
    if (!check(u, path.cost, path.delay)) {
        return;
    }
    
    double p = static_cast<double>(rand() % 100) / 100;
    // Use dominance check to prune branches only if there
    // is no delay lower bound.
    if (flow_.delay_lb <= 0 && !update(u, path, p)) {
        std::cout<<"return for update\n";
        return;
    }
    */
    for (Link* link : graph_->GetEgressLinks(u)) {
        NodeId ter = link->ter_id;
        //std::cout<<ter;
        std::vector<int> temp_units = path.C_units;
        int temp_cost = path.cost;
        int temp_delay = path.delay;
        std::vector<int> test = Intersection(path.C_units, link->A_units);
        
        if(test.size()==0){  //若可用units为空集则continue
            std::cout<<ter<<"continue for connect\n";
            continue;
        } 
        if (visited_[ter-1]) {  //若该节点已经访问过则continue
            continue;
        }
        if(link->cost>0){
            path.cost += link->cost;
            if(path.cost>limit_cost){  //若cost已经大于最大cost则continue
                continue;
            }
        }else{
            // cost小于零代表开启中继站
            path.cost = 0;
            path.C_units = Omega;
        }
        path.C_units = test;
        visited_[ter-1] = true;
        path.delay += link->delay;
        path.path_info.push_back(ter);
        Dfs(ter, path);
        path.cost = temp_cost;
        path.delay = temp_delay;
        path.C_units = temp_units;
        path.path_info.pop_back();
        visited_[ter-1] = false;
    }
}

bool Pulse_optical::check(NodeId u, int cost, int delay) {
    if (cost_map_[u-1] + cost > limit_cost)
        return false;
    if (delay_map_[u-1] + delay > tmp_min_delay)
        return false;
    return true;
}

bool Pulse_optical::update(NodeId u, const Path& path, double p) {
    // Update the path with minimum cost
    if (info_[u].min_cost_path.cost > path.cost) {
        info_[u].min_cost_path = path;
        return true;
    }
    if (info_[u].min_cost_path.delay <= path.delay && Judge(path.C_units, info_[u].min_cost_path.C_units)) {
        return false;
    }
    // Update the path with minimum delay
    if (info_[u].min_delay_path.delay > path.delay) {
        info_[u].min_delay_path = path;
        return true;
    }
    if (info_[u].min_delay_path.cost <= path.cost && Judge(path.C_units, info_[u].min_delay_path.C_units)){
        return false;
    }
    //Update the path with maximum units
    if(Judge(info_[u].max_units_path.C_units, path.C_units)){
        return true;
    }

    if((info_[u].max_units_path.cost<=path.cost) && (info_[u].max_units_path.delay <=path.delay) && 
        (Judge(path.C_units, info_[u].max_units_path.C_units))){
        return false;
    }
    // if not meet the requirements above,
    // update the random replace path
    if ((info_[u].random_rep_path.delay <= path.delay) &&
        (info_[u].random_rep_path.cost <= path.cost)&&
        (Judge(path.C_units, info_[u].random_rep_path.C_units))) {
        return false;
    }
    if (p > 0.5) {
        info_[u].random_rep_path = path;
    }
    return true;
};
/*
void Pulse_optical::print() const{
     std::vector<Path> buf;
    for (int i = 0; i < results_.size(); ++i) {
        if (results_[i].delay >= flow_.delay_lb &&
            results_[i].delay <= flow_.delay_ub) {
            buf.push_back(results_[i]);
        }
    }
    results_.back().Print();
}
*/